<?php
/*
 * words中都是不同的词，如果其中str1加str2之后是回文串，则str1的位置和str2的位置我们需要收集。
 * 比如words = ["bat", "tab", "cat"]
 * 返回[[0, 1], [1, 0]]
 * words = ["abcd", "dcba", "lls", "s", "sssll"]
 * 返回[[0, 1], [1, 0], [3, 2], [2, 4]]
 */

$arr = ["abcd", "dcba", "lls", "s", "sssll"];
$obj = new Code_05_PalindromePairs();
$obj->do($arr);
$obj->printResult();

class Code_05_PalindromePairs
{
    public $result = [];

    /*
     * 思路：
     * 对于一个word
     * 1、将其逆序后的字符串如果在词典里可以配对成回文
     * 2、找到包含第一个字符的字符串是回文的部分，将其他后续的子串逆序后的字符串如果在词典可以配对成回文
     * 3、找到包含最后一个字符的字符串是回文的部分，将其他前面的子串逆序后的字符串如果在词典可以配对成回文
     *
     * 对于第2、3点，可以参考manacher算法
     * https://www.jianshu.com/p/116aa58b7d81
     * https://www.cnblogs.com/cloudplankroader/p/10988844.html
     * https://www.zhihu.com/question/37289584
     */
    public function do($arr)
    {
//        $arr = ['acbbcbds'];
        $hashMap = [];
        foreach ($arr as $k => $v) {
            $hashMap[$v] = $k;
        }
        for ($i = 0, $len = count($arr); $i < $len; $i++) {
            $this->findAll($arr[$i], $i, $hashMap);
        }
        return $this->result;
    }

    public function findAll($word, $index, $hashMap)
    {
        $reverse = strrev($word);
        // 思路1
        if ($word != $reverse && array_key_exists($reverse, $hashMap)) {
            $this->addRecord($index, $hashMap[$reverse]);
            $this->addRecord($hashMap[$reverse], $index);
        }
        // 思路2
        $radius = $this->manacher($word);
        $mid = (count($radius)) >> 1;
        for ($i = 1; $i < $mid; $i++) {
            if ($i - $radius[$i] == -1) {
                $sub = substr($reverse, 0, $mid-$i);
                if (array_key_exists($sub, $hashMap) && $hashMap[$sub] != $index) {
                    $this->addRecord($hashMap[$sub], $index);
                }
            }
        }
        //思路3
        for ($i = $mid + 1; $i < count($radius); $i++) {
            if ($i + $radius[$i] == count($radius)) {
                $sub = substr($reverse, 0, ($mid << 1) - $i);
                if (array_key_exists($sub, $hashMap) && $hashMap[$sub] != $index) {
                    $this->addRecord($hashMap[$sub], $index);
                }
            }
        }
    }

    // 获取回文半径数组radius
    public function manacher($word)
    {
        $mchs = $this->manacherString($word);
        $len = count($mchs);
        $radius = array_fill(0, $len, 0);
        //r是最右回文边界，center是回文中心
        $center = -1;
        $r = -1;
        for ($i = 0; $i != $len; $i++) {
            //第一步直接取得可能的最短的回文半径，当i>R时，最短的回文半径是1，反之，最短的回文半径可能是i对应的i'的回文半径或者i到R的距离
            //$radius[$i] = $r > $i ? min($radius[2 * $center - $i], $r - $i) : 1;
            if ($r > $i) {
                $radius[$i] = min($radius[2 * $center - $i], $r - $i);
            } else {
                $radius[$i] = 1;
            }
            //取最小值后开始从边界暴力匹配，匹配失败就直接退出
            while ($i + $radius[$i] < $len && $i - $radius[$i] > -1) {
                if ($mchs[$i + $radius[$i]] != $mchs[$i - $radius[$i]]) {
                    break;
                }
                $radius[$i]++;
            }
            //观察此时r和center是否能够更新
            if ($i + $radius[$i] > $r) {
                $r = $i + $radius[$i];
                $center = $i;
            }
        }
        return $radius;
    }

    // word的每一个字符左右都加#符号，长度变成了 2n+1 必定奇数
    public function manacherString($word)
    {
        $chs = str_split($word);
        $mchs = array_fill(0, count($chs) * 2 + 1, null);
        $index = 0;
        for ($i = 0, $len = count($mchs); $i != $len; $i++) {
            $mchs[$i] = ($i & 1) == 0 ? '#' : $chs[$index++];
        }
        return $mchs;
    }

    public function addRecord($a, $b)
    {
        $arr = [$a, $b];
        !in_array($arr, $this->result) && $this->result[] = [$a, $b];

    }

    public function printResult()
    {
        print_r($this->result);
    }

}